package com.jinxi.algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * @Autho changqi.wu
 * @Date 路在脚下，使劲踩！
 */
public class CommonFather {

    private TreeNode init(){

        TreeNode node1 = new TreeNode(3);
        TreeNode node2 = new TreeNode(5);
        TreeNode node3 = new TreeNode(1);

        TreeNode node4 = new TreeNode(6);
        TreeNode node5 = new TreeNode(2);
        TreeNode node6 = new TreeNode(0);
        TreeNode node7 = new TreeNode(8);
        TreeNode node8 = new TreeNode(7);
        TreeNode node9 = new TreeNode(4);

        node1.left = node2;
        node1.right = node3;

        node2.left = node4;
        node2.right = node5;

        node3.left = node6;
        node3.right = node7;

        node3.left = node6;
        node3.right = node7;

        node5.left = node8;
        node5.right = node9;

        return  node1;
    }

    public static void main(String[] args) {

        CommonFather f = new CommonFather();
        TreeNode root = f.init();

        TreeNode p = new TreeNode(5);
        TreeNode q = new TreeNode(1);

        TreeNode com = f.lowestCommonAncestor(root, p, q);

        System.out.println(com.val);

    }


    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        List<TreeNode> foot1 = new ArrayList();
        traverse(root, p, foot1);
        List<TreeNode> foot2 = new ArrayList();
        traverse(root, q, foot2);
        int size = foot1.size() > foot2.size() ? foot2.size() : foot1.size();
        for (int i = 0; i < size; i++) {
            TreeNode node1 = foot1.get(i);
            TreeNode node2 = foot2.get(i);
            if(node1 == null || node2 == null){
                return foot1.get(i - 1);
            }
            if (node1.val != node2.val) {
                return foot1.get(i - 1);
            }
        }
        return null;
    }


    public void traverse(TreeNode root, TreeNode node, List<TreeNode> foots) {
        if(foots.contains(null)){
            return;
        }
        if (root.val == node.val) {
            foots.add(root);
            foots.add(null);
            return;
        }
        foots.add(root);
        if (root.left != null) {
            root = root.left;
            traverse(root, node, foots);
        }
        if (root.right != null) {
            root = root.right;
            traverse(root, node, foots);
        }

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

}
